package problem918;

//918.环形子数组的最大和
//https://leetcode.cn/problems/maximum-sum-circular-subarray/

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int sum = 0;
        for(int x:nums) {
            sum += x;
        }
        int fmax = maxSubarraySum(nums); //最大子数组和
        int fmin = minSubarraySum(nums); //最小子数组和
        return Math.max(fmax, sum==fmin?Integer.MIN_VALUE:sum-fmin);
    }

    private int maxSubarraySum(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        int ret = dp[0];
        for(int i = 1; i<n; i++) {
            dp[i] = Math.max(dp[i-1]+nums[i], nums[i]);
            ret = Math.max(ret, dp[i]);
        }
        return ret;
    }

    private int minSubarraySum(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        int ret = dp[0];
        for(int i = 1; i<n; i++) {
            dp[i] = Math.min(dp[i-1]+nums[i], nums[i]);
            ret = Math.min(ret, dp[i]);
        }
        return ret;
    }
}

/*
如果数组⾸尾相连的⼀部分是最⼤的数组和，那么数组中间就会空出来⼀部分；
因为数组的总和sum 是不变的，那么中间连续的⼀部分的和⼀定是最⼩的；
因此，我们就可以得出⼀个结论，对于第⼆种情况的最⼤和，应该等于sum - fmin ，其中
fmin 表⽰数组内的「最⼩⼦数组和」。
5,-3,5 , 5,-3,5

*/